1. Technical Field
The present invention relates to apparatus and methods for analyzing a computer system.
2. Prior Art
The state of the art in system verification and related technologies is represented by the following documents:
[1] A. Aharon, D Goodman, M. Levinger, Y. Lichtenstein, Y. Malka, C. Metzger, M. Molcho, and G. Shurek. Test program generation for functional verification of PowerPC processors in IBM. In 32nd Design Automation Conference, DAC 95, pages 279-285, 1995.
[2] Y. Lichtenstein, Y. Malka, and A. Aharon. Model-based test generation for processor design verification. In Innovative Applications of Artificial Intelligence (IAAI). AAAI Press, 1994.
[3] Published European Patent Application No. 84303181.5 (Publication No. 0 628 911 A2) to International Business Machines Corporation.
[4] D. Marr, S. Thakkar and R. Zucker. Multiprocessor Validation of the Pentium Pro Microprocessor, Proceedings of the COMPCON""96
[5] J. Walter et al., Hierarchical Random Simulation Approach for the Verification of S/390 CMOS Multiprocessors, Proceedings of the DAC""97 (pages: 89-94)
[6] K. Hines and G. Borriello. Dynamic Communication Models in Embedded System Co-Simulation, Proceedings of the DAC""97 (pages:395-400)
[7] M. Bauer and W. Ecker. Hardware/Software Co-Simulation in a VHDL-based Test Bench Approach, Proceedings of the DAC""97 (pages:774-779)
[8] U.S. Pat. No. 5,740,353 to Kreulen et al.
The disclosures of all publications mentioned in the specification and of the publications cited therein are hereby incorporated by reference.
The present invention seeks to provide improved apparatus and methods for system analysis.
Analysis can be understood to include verification, testing, debugging and performance analysis. The application of synchronization in system verification is now described in detail.
Hardware system verification is an integral, important activity in the development of every new computer system.
The target of system verification is to clean the design from functional errors, called bugs, before manufacturing begins. System design errors may originate from different sources: inconsistent interfaces between the system components can be the result of separate design efforts; errors may escape from the process of verifying a component of the system; other reasons exist for system errors. Overall, the target of system verification is to verify whether the design of the system complies with its specification. It is important that system verification exposes such errors before the system is manufactured, as the cost of correcting a bug after manufacturing can become very high.
One method used for hardware system verification is simulation of a system model. Each system model is composed of the designs of the system components. In addition, behavioral units may be added to the model in order to simulate the behavior of system components such as peripherals.
Verification of system behavior is achieved by simulation of test programs. System test programs are composed of the execution threads for each of the system components. These system tests can be automatically generated by an automatic test generation tool. (Documents 1 and 2 listed above in the Background section describe a test generation tool for a single processor.)
System simulation models can become very large, including: several processors, several bus bridges, memory controllers and I/O bus behaviorals. The simulation of tests on such a model is time consuming. A good verification coverage cannot be obtained by mere massive simulation of many random tests. A method for increasing the quality of system tests is to force interesting sequences of events by synchronizing between different system components. Furthermore, good coverage can be obtained by testing all possible orderings of a single set of events. This can be achieved by using the synchronization method described in this invention.
System verification is based on test-programs, which are rather complex. Compared to the test-programs used in processor verification, system test-programs require the synchronization of different, independent system components. System activity is determined by a set of distributed protocols, which exhibit a lack of central control. The sequence in which the system components interact is test-variant. Good coverage of the verification-plan is obtained by different sequence combinations. And thus, the ability to control the synchronization of the system components during a test is important for efficient system verification.
System verification may be based on automatic test-program generation. The input to an automatic test-program generation tool may comprise a list of test generation directives and the output may comprise a test-program which includes the initialization and execution directives to all system components, as well as expected results. Test synchronization should be integrated into the test generation methodology in order to utilize the productivity of design-automation tools. Furthermore, test synchronization should provide the flexibility to control the delay between the synchronized system components. Short delays increase the contentions between system activities and eventually lead to the detection of design errors.
Several methods exist for implementing synchronizations among agents. The following features are important for a preferred synchronization method:
Fast speedxe2x80x94As few cycles as possible between the signaling event and the pending transaction. Experience shows that the smaller the synchronization delay, the higher the chances are for resource contention. In other words, the time it takes for the waiting agent to start executing the pending transaction after the signaling event is critical to achieve tight interaction.
Generic Applicabilityxe2x80x94Usability by different types of agents, including non-initiating system components, e.g., memory controllers.
Conventional testing systems depend on the type of the component they target. There are synchronization mechanisms developed for processors, and there are techniques applicable to different behaviorals, depending on the specifics of each of them, e.g. system verification: [Documents 4 and 5 listed above in the Background sections; handshake synchronization: [Document 6]; master synchronizer: [Document 7].
The present invention seeks to provide a method for synchronization which generally achieves the shortest time possible between the signaling event and the pending transaction; and also can be used with processors, I/O devices and non-initiating system components that have access to a bus. This is an efficient, strong synchronization method for use in bus-based systems. A preferred embodiment of the present invention seeks to provide a method for synchronization by means of controlling bus arbitration. This embodiment preferably comprises a SC (synchronization controller) program.
The system of the present invention may be used during normal multi-component system operation. One preferred embodiment of the present invention comprises a technique to improve verification quality. Verification typically comprises about 50% of the design effort of a new system, resulting in costs of billions of dollars. The synchronization technique described herein targets resource contention, an area notorious for containing design bugs and very hard to simulate in random verification. One objective of a preferred embodiment of the present invention is, therefore, to make system verification efforts more efficient by targeting problem areas in a limited amount of simulation time.
A particular feature of a preferred embodiment of the present invention is that the synchronization provided thereby can be described on the architectural level but works as well at any implementation level synchronization. It can be used with generally any bus protocol that uses bus arbitration to control bus transaction order.
Typically, this invention employs simulators that provide an API to external code that can poll and change simulation signals during simulation. Modern simulators such as ModelSim/VHDL and Synopsis VHDL System Simulation (VSS), commercially available from Model Technology Inc. and Synopsis Inc. respectively, have this capability. The method is general enough to apply to a wide range of system verification problems in which the bus protocol uses arbitration, as most bus protocols today do.
The arbitration synchronization mechanism of the present invention is suitable, for example, for AS/400 and RS/6000 system verification, as well as for the verification of other devices that sit on a bus such as an L2 cache-controller.
Bus arbitration synchronization is, in at least some applications, the fastest non-intrusive way to release an agent connected to a bus. Possible applications for bus arbitration synchronization include the following:
a. A synchronization controller which is used in the automation of the system verification process;
b. Manual testing process, to detect bugs in the design.
c. Manual debugging process to identify causes for malfunction in a design.
d. Performance analysis including all methods for evaluating expected performance of a given design of a hardware system. For example, the bus arbitration synchronization of the present invention can be used to establish a given level of bus utilization in the evaluated system.
The synchronization scheme shown and described herein is very useful in system testing to achieve control of sequences. As the complexity of designed systems grows in the number of components and functionality, the emphasis of verification increasingly moves towards system verification, enhancing the usefulness of arbitration synchronization as a sophisticated method in system testing.
Terminology:
Agent (or Device)xe2x80x94A system component that is attached to a bus. The component is able to request arbitration on the bus (address and/or data buses) and then to be the bus master for a bus tenure. For example, a processor can be the bus master for an address tenure on a split address/data bus, and also for write data tenures. On the other hand, a memory controller can only be the bus master for read data tenures.
Agent Typexe2x80x94For example, PowerPC 603 processor, PCI device.
Arbitrationxe2x80x94When there are several system components attached to a bus, a mechanism is used for assuring that two system components do not write to the bus at the same time. This mechanism is known as arbitration and is enforced by the use of an arbiter system component also attached to the bus. Frequently, each system component on the bus requests access to the bus via request lines, and is granted access to the bus via grant lines.
Arrival at the Stationxe2x80x94A point in time at which the waiting agent has completed the transaction before the pending transaction and therefore is on the verge of executing its pending transaction.
Behavioralxe2x80x94Behaviorals are used during system verification to simulate the behavior of peripheral (I/O) devices, or to take on the role of extra agents that are not real designs.
Busxe2x80x94A bus serves as a shared communication link among system components over which addresses and data are passed.
Initiating agentxe2x80x94An agent that may place an address on its associated bus.
Non-initiating agentxe2x80x94An agent that never places an address on its associated bus, but may be the supplier of data on the bus.
Reference Modelxe2x80x94A reference model for a system predicts the effect certain inputs have on the system state. By use of reference models during test generation, the generator can estimate the current state of the system resources that are interesting to the test.
Eventxe2x80x94A certain occurrence of a significant bus/agent state during simulation run time. (e.g. the occurrence of an address-phase in a PCI bus.)
Signaling agent/devicexe2x80x94Agent at which an event (xe2x80x9csignaling eventxe2x80x9d) is to occur which will serve as a condition for operation of another agent (termed xe2x80x9cwaiting agentxe2x80x9d or xe2x80x9cpending agentxe2x80x9d). Until signaling event occurs at signaling agent, operation of waiting/pending agent is held up.
Synchronizationxe2x80x94Synchronization preserves the ordering of a sequence of events. For example, synchronization can be used to force one agent to write to address A only after another agent has completed its access to A. The agent that waits is referred to as the waiting (or pending) agent/device. The waiting agent does not continue its execution until a predetermined event occurs which is termed the signaling event. Once the signaling event occurs, the waiting agent""s pending transaction executes.
Synchronization Controller (SC)xe2x80x94The purpose of a synchronization controller is to ensure a given sequence of events. During simulation, the existence of a simulation control program that runs concurrently with the simulation is assumed. This program, the synchronization controller (SC), is able to monitor the current system state and also to enforce synchronizations among agents. The SC has the ability to monitor system signals and also to force a system signal to change to a new specific value.
Test generatorxe2x80x94A process that generates tests in order to be simulated for the purpose of verification.
Tight snoopingxe2x80x94This is any event sequence in which two agents access the same system resource, e.g., memory location, close in time.
Timexe2x80x94In this invention disclosure, it is assumed that time is measured in terms of simulationxe2x80x94or clockxe2x80x94cycles.
Transactionxe2x80x94For the purposes of this invention disclosure, a transaction is defined as any operation of an agent that is reflected on the agent""s external interface to the rest of the system model.
Tenurexe2x80x94A bus tenure is an interval of time in which one type of information is placed on the bus. For example, during a processor read from memory, there will be 2 tenures, an address tenure and a data tenure. During the address tenure, the processor will place the address on the bus. During the data tenure, the memory controller will place the requested data on the bus.
De-assertedxe2x80x94de-activated.
Eieioxe2x80x94The PowerPC architecture specification includes the eieio instruction (see xe2x80x9cPowerPC 601 RISC Microprocessor User""s Manualxe2x80x9d, 1993). This instruction results in an eieio transaction on the bus. Eieio is used in the present specification simply as an example of an instruction that results in a bus transaction that does not appear on the bus for any other purpose during the test simulation. The requirement is for a dedicated bus transaction that the synchronization controller is able to interpret as a signal to it from a waiting agent that is ready for its pending transaction.
There is thus provided in accordance with a preferred embodiment of the present invention a synchronization method including running a system having multiple agents in parallel operation, and forcing synchronization order between the multiple agents at at least one intervention juncture.
Further in accordance with a preferred embodiment of the present invention the multiple agents include at least two agents accessing a single address at almost the same time and wherein the forcing step includes forcing a predetermined one of the two agents to access the address before the other one of the two agents accesses the address.
Still further in accordance with a preferred embodiment of the present invention the multiple agents include first and second agents and wherein the forcing step includes forcing order between the first and second agents at a first intervention juncture, and wherein the multiple agents include third and fourth agents, at least one of which differs from the first and second agents, and wherein the forcing step also includes forcing order between the third and fourth agents at a second intervention juncture which is different from the first intervention juncture.
Still further in accordance with a preferred embodiment of the present invention the multiple agents include a plurality of threads on an individual processor.
Additionally in accordance with a preferred embodiment of the present invention the multiple agents include at least three agents in parallel operation at at least one intervention juncture.
Further in accordance with a preferred embodiment of the present invention the multiple agents include at least one signaling agents executing at least one signaling events and at least one waiting agents executing at least one pending transactions, and wherein the forcing step includes holding up operation of the at least one waiting agents until the at least one signaling agents execute the at least one signaling events.
Still further in accordance with a preferred embodiment of the present invention the at least one signaling events include a plurality of signaling events and wherein the forcing step includes holding up operation of the at least one waiting agents until the plurality of signaling events have been executed.
Additionally in accordance with a preferred embodiment of the present invention the at least one pending transactions include a plurality of pending transactions and wherein the forcing step includes delaying the plurality of pending transactions until the at least one signaling events have been executed.
Further in accordance with a preferred embodiment of the present invention the three agents include a first agent accessing an address which accessing operation must occur before a second agent and a third agent access the same cache line generally simultaneously.
Still further in accordance with a preferred embodiment of the present invention the multiple agents in parallel operation are operative to fill at least one buffer of a bus bridge.
Additionally in accordance with a preferred embodiment of the present invention the multiple agents in parallel operation are operative to fill at least one buffer of a memory controller.
There is also provided, in accordance with another preferred embodiment of the present invention, synchronization apparatus including a system manipulator operative to run a system having multiple agents in parallel operation, and an order imposer operative to force synchronization order between the multiple agents at at least one intervention juncture.
Additionally in accordance with a preferred embodiment of the present invention the multiple agents participate in a plurality of events and the forcing step includes forcing the plurality of events to occur in all possible orders.
Further in accordance with a preferred embodiment of the present invention the at least one signaling agents include a plurality of signaling agents executing at least one signaling events and wherein the forcing step includes holding up operation of the at least one waiting agents until the plurality of signaling agents executes the at least one signaling events.
Still further in accordance with a preferred embodiment of the present invention the at least one waiting agents includes a plurality of waiting agents and wherein the forcing step includes holding up operation of the plurality of waiting agents until the at least one signaling agents execute the at least one signaling event.
There is also provided, in accordance with another preferred embodiment of the present invention, a synchronization method including running a system having multiple agents in parallel operation, the multiple agents each having at least one path to a common bus, and using a bus arbitration mechanism to synchronize between the multiple agents in accordance with a predetermined scheme, including blocking at least one individual agent""s path to the common bus if the scheme indicates that the individual agent is not to be activated, and restoring the at least one individual agent""s path to the common bus once the scheme indicates that the individual agent can be activated.
Further in accordance with a preferred embodiment of the present invention the multiple agents include a plurality of processors.
Still further in accordance with a preferred embodiment of the present invention the multiple agents include at least one processor and at least one I/O unit.
Additionally in accordance with a preferred embodiment of the present invention the multiple agents include at least one agent having a path onto the common bus via at least one intermediate bus.
Further in accordance with a preferred embodiment of the present invention the using step is performed externally to and therefore independently of the internal structure of each of the agents.
Still further in accordance with a preferred embodiment of the present invention the using step includes forcing architectural signals.
Additionally in accordance with a preferred embodiment of the present invention the multiple agents include at least two agents accessing a single address at almost the same time and wherein the using step includes forcing a predetermined one of the two agents to access the address before the other one of the two agents accesses the address.
Further in accordance with a preferred embodiment of the present invention the multiple agents include first and second agents and wherein the using step includes forcing order between the first and second agents at a first intervention juncture, and wherein the multiple agents include third and fourth agents, at least one of which differs from the first and second agents, and wherein the using step also includes forcing order between the third and fourth agents at a second intervention juncture which is different from the first intervention juncture.
Still further in accordance with a preferred embodiment of the present invention the multiple agents are operative to fill at least one buffer of a memory controller and wherein the using step includes preventing the memory controller from accessing the common bus.
Additionally in accordance with a preferred embodiment of the present invention the multiple agents are operative to fill at least one buffer of a bus bridge and wherein the using step includes preventing the bus bridge from accessing the common bus.
There is further provided, in accordance with another preferred embodiment of the present invention, a synchronization apparatus including a system manipulator operative to run a system having multiple agents in parallel operation, the multiple agents each having at least one path to a common bus, and a bus arbitration mechanism operative to synchronize between the multiple agents in accordance with a predetermined scheme, including blocking at least one individual agent""s path to the common bus if the scheme indicates that the individual agent is not to be activated, and restoring the at least one individual agent""s path to the common bus once the scheme indicates that the individual agent can be activated.
Further in accordance with a preferred embodiment of the present invention the system manipulator includes a system simulator operative to simulate the system.
Still further in accordance with a preferred embodiment of the present invention the system manipulator includes a performance analyzer operative to conduct a performance analysis of the system.
Additionally in accordance with a preferred embodiment of the present invention the system manipulator includes a system verifier operative to verify the system.
Further in accordance with a preferred embodiment of the present invention the system manipulator includes a system debugger operative to debug the system.
Still further in accordance with a preferred embodiment of the present invention the running step includes simulating the system.
Additionally in accordance with a preferred embodiment of the present invention the running step includes conducting a performance analysis of the system.
Further in accordance with a preferred embodiment of the present invention the running step includes verifying the system.
Additionally in accordance with a preferred embodiment of the present invention the running step includes debugging the system.